#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
class Trie
{
private:
    vector<Trie *> child;
    bool isLeaf;

public:
    Trie() : isLeaf(false)
    {
        this->child = vector<Trie *>(26, nullptr);
    }
    void insert(string word)
    {
        Trie *p = this;
        for (char w : word)
        {
            int t = w - 'a';
            if (!p->child[t])
                p->child[t] = new Trie();
            p = p->child[t];
        }
        p->isLeaf = true;
    }
    bool startWith(string prefix)
    {
        Trie *p = this;
        for (auto &w : prefix)
        {
            int t = w - 'a';
            if (!p->child[t])
                return false;
            p = p->child[t];
        }
        return true;
    }
};

class Solution
{
public:
    int countPrefixes(vector<string> &words, string s)
    {
        int ans = 0, sLen = s.length();
        for (int i = 0; i <= sLen; i++)
        {
            cout << s.substr(0, i) << endl;
            ans += count(words.begin(), words.end(), s.substr(0, i));
        }
        return ans;
    }

    int countPrefixes_2(vector<string> &words, string s)
    {
        int ans = 0;
        Trie trie;
        trie.insert(s);
        for (string word : words)
        {
            if (trie.startWith(word))
            {
                ans++;
            }
        }
        return ans;
    }

    int countPrefixes_3(vector<string> &words, string s)
    {
        unordered_set<string> set1;
        int n = s.size();
        for (int i = 0; i < n; ++i)
        {
            set1.insert(s.substr(0, i + 1));
        }
        int res = 0;
        for (auto &s : words)
        {
            if (set1.count(s))
            {
                res++;
            }
        }
        return res;
    }
};
int main()
{
    Solution s;
    vector<string> words = {"a", "b", "c", "ab", "bc", "abc"};
    string str = "abc";
    cout << s.countPrefixes_2(words, str) << endl;
    system("pause");
    return 0;
}
